//给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。 
//
// （当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。） 
//
// 示例 1: 
//
// 输入: N = 10
//输出: 9
// 
//
// 示例 2: 
//
// 输入: N = 1234
//输出: 1234
// 
//
// 示例 3: 
//
// 输入: N = 332
//输出: 299
// 
//
// 说明: N 是在 [0, 10^9] 范围内的一个整数。 
// Related Topics 贪心 数学 
// 👍 216 👎 0

package com.cute.leetcode.editor.cn;
public class MonotoneIncreasingDigits {
    public static void main(String[] args) {
        new MonotoneIncreasingDigits().new Solution().monotoneIncreasingDigits(10);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 咋说呢，我也不知道为什么能过
         * 写了一个方法去查这个数是否是单增的，如果是单增的返回-1，如果不是返回下标i
         * 然后将i处的值--，将i之后的值全赋值为9，再次循环
         */
        public int monotoneIncreasingDigits1(int n) {
            char[] chars = (n + "").toCharArray();///转换成字符数组便于处理
            for (int i = n; i >= 0 ;) {
                int h = helper(i);
                if (h == -1) return i;//如果当前数是单增的，直接返回
                chars[h]--;//出现递减的一位-1，将之后的所有位都置为9，得到新的num
                for (int j = h+1; j < chars.length ; j++)
                    chars[j] = '9';
                i = Integer.parseInt(new String(chars));
                chars = (i + "").toCharArray();//更新数组，如果有前导0的话这样可以去掉前导0
            }
            return 0;
        }
        public int helper(int num){
            String s = num+"";
            int len = s.length();
            for (int i = 0; i < len-1; i++) {
                if (s.charAt(i)>s.charAt(i+1)) return i;
            }
            return -1;
        }

        /**
         * 代码随想录的题解：贪心算法--->从后向前遍历，index记录置9的起始位置
         * 以332为例，第一次遍历后 num = 322 index = 2
         * 第二次遍历后 num = 222 index = 1
         * 然后从index开始全部赋值为9
         */
        public int monotoneIncreasingDigits(int n) {
            char[] chars = (n + "").toCharArray();
            int index = chars.length;
            int len = chars.length;
            for (int i = len-1; i > 0; i--) {
                if (chars[i-1]>chars[i]){
                    chars[i-1]--;
                    index = i;
                }
            }
            for (int i = index; i < len; i++) {
                chars[i] = '9';
            }
            return Integer.parseInt(new String(chars));
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}